//
//  AI.swift
//  Chess5
//
//  Created by sun on 2017/3/28.
//  Copyright © 2017年 apple. All rights reserved.
//

import Foundation

public enum Role : Int {
    
    case empty // chess[][] is empty
    
    case computer // [][] put computer
    
    case human // [][] human's chess
}

public class Lian {
    static let five = 100000
    static let four = 10000 // 活2
    static let three = 1000 // 活2，冲4
    static let two = 100
    static let one = 10
    static let zero = 1 // 死1
}

public struct Position {
    var x: Int,y: Int
}

class AI{
    
    let MAX: Int = 4 * Lian.five
    let MIN: Int = -4 * Lian.five
    let N: Int = 15
    var hitCache = 0
    
    var pScore: [[[Int]]]
//    var humScore: [[[Int]]]
    var zobrist: Zobrist
    var scoreCache: Dictionary<Int64, Int>
    var vis:[[Bool]]
    var board: [[Role]]
    
    let direction = [[1, 0],[-1, 0],[0, 1],[0, -1],[1, 1],[-1, -1],[1, -1],[-1, 1]]
    
    var searchCnt = 0
    var scoreCnt = 0
    var pointsCnt = 0
    var cacheCnt = 0
    var removeCnt = 0
    var calculateCnt = 0
    var goCnt = 0
    var ABcut = 0
    var pEvaluate = 0
    
    init() {
        pScore = [[[Int]]]()
//        humScore = [[[Int]]]()
        board = [[Role]]()
        vis = [[Bool]]()
        
        for _ in 0..<N {
            var cRow = [[Int]]()
            var hRow = [[Int]]()
            var vRow = [Bool]()
            var row = [Role]()
            for _ in 0..<N {
                var cs = [Int]()
                var hs = [Int]()
                for _ in 0..<5 {
                    cs.append(0)
                    hs.append(0)
                }
                cRow.append(cs)
                hRow.append(hs)
                vRow.append(false)
                row.append(Role.empty)
            }
            pScore.append(cRow)
//            humScore.append(hRow)
            vis.append(vRow)
            board.append(row)
        }
        
        zobrist = Zobrist()
        scoreCache = Dictionary();

    }
    
    func reset()  {
        for i in 0..<N {
            for j in 0..<N {
                vis[i][j] = false
                board[i][j] = .empty
                for k in 0..<5 {
                    pScore[i][j][k] = 0
//                    humScore[i][j][k] = 0
                }
            }
        }
        zobrist = Zobrist()
        scoreCache.removeAll()
        hitCache = 0
    }
    func resetRecord() {
        searchCnt = 0
        scoreCnt = 0
        pointsCnt = 0
        cacheCnt = 0
        removeCnt = 0
        calculateCnt = 0
        goCnt = 0
        ABcut = 0
        pEvaluate = 0
    }
    
//    var queue: DispatchQueue = DispatchQueue(label: "AI.queue")
    
    // 9万次,但是有个200的常数，80秒，不能忍
    func findPlace(board: inout [[Role]]) -> Position {
        
        resetRecord()
        
        var bestPlace = [Position]()
        
        var maxScore: Int = MIN
        let deep = 2
        let alpha = MAX
        let beta = MIN

        let positions = generatePositions(board: board, deep: 2)
        
        for i in 0..<positions.count {
            let p = positions[i]
            go(board: &board, player: Role.computer, p: p)
            let v = min(board: &board, deep: deep, alpha: Int(alpha), beta: Int(beta))
            remove(board: &board, p: p)
            // find the better one ,remove all
            if maxScore < v {
                maxScore = v
                bestPlace.removeAll()
                bestPlace.append(p)
            }
            else if maxScore == v {
                bestPlace.append(p)
            }
            
        }
        printRecord()
        
        let randomIdx: Int = Int(arc4random_uniform(UInt32(bestPlace.count)))
        return bestPlace[randomIdx]
    }
    func printRecord() {
        print("max | min 函数：",searchCnt)
        print("点评估次数：",pEvaluate)
        print("ab剪枝的次数",ABcut)
        print("score棋局评估次数：", scoreCnt)
        print("棋局cache中元素个数:",scoreCache.count)
        print("remove函数：",removeCnt)
        print("calculate函数：",calculateCnt)
        print("go函数：",goCnt)
        print("----------------------------")
    }

    
    // computer or human go one chess
    func go(board: inout [[Role]],player: Role,p: Position)  {
        goCnt += 1
        board[p.x][p.y] = player
        var pCode: Int64
        // set empty
        if player == Role.computer {
            pCode = Int64(zobrist.comCode[p.x][p.y])
        }
        else {
            pCode = Int64(zobrist.humCode[p.x][p.y])
        }
        zobrist.code ^= pCode
        update(board: board, p: p, player: player)
    }
    
    // computer or human remove one chess
    func remove(board: inout [[Role]],p: Position) {
        removeCnt += 1
        let player = board[p.x][p.y]
        board[p.x][p.y] = Role.empty
        var pCode: Int64
        // find player code
        if player == Role.computer {
            pCode = Int64(zobrist.comCode[p.x][p.y])
        }
        else {
            pCode = Int64(zobrist.humCode[p.x][p.y])
        }
        zobrist.code ^= pCode
        update(board: board, p: p,player: player)
    }

    func calculate(count: Int, empty: Int, block: Int) -> Int {
        calculateCnt += 1
        var result: Int = 0
        
        // 棋子之间没有空位
        if empty <= 0 {
            if count >= 5 {
                result = Lian.five
            }
            else {
                if block == 0 {
                    switch count {
                    case 4:
                        result = Lian.four
                    case 3:
                        result = Lian.three
                    case 2:
                        result = Lian.two
                    case 1:
                        result = Lian.one
                    default:
                        result = 0
                    }
                }
                else if block == 1 {
                    switch count {
                    case 4:
                        result = Lian.three
                    case 3:
                        result = Lian.two
                    case 2:
                        result = Lian.one
                    case 1:
                        result = Lian.zero
                    default:
                        result = 0
                    }
                }
            }
        }
        else if empty == 1 || empty == count - 1 {
            if count >= 6 {
                result = Lian.five
            }
            else {
                if block == 0 {
                    switch count {
                    case 5:
                        result = Lian.four
                    case 4,3:
                        result = Lian.three
                    case 2:
                        result = Lian.two
                    default:
                        result = 0
                    }
                }
                else if block == 1 {
                    switch count {
                    case 5:
                        result = Lian.three // *0*00001,是冲4，而10*0000*是活4
                    case 4:
                        result = Lian.three
                    case 3:
                        result = Lian.two
                    case 2:
                        result = Lian.one
                    default:
                        result = 0
                    }
                }
                else if block == 2 {
                    switch count {
                    case 5,4:
                        result = Lian.three
                    default:
                        result = 0
                    }
                }
            }
        }
        else if empty == 2 || empty == count - 2 {
            if count >= 7 {
                result = Lian.five
            }
            else {
                if block == 0 {
                    switch count {
                    case 6:
                        result = Lian.four
                    case 5:
                        result = Lian.three // 冲4
                    case 4:
                        result = Lian.three // 冲4
                    default:
                        result = 0
                    }
                }
                else if block == 1 {
                    switch count {
                    case 6:
                        result = Lian.four //*00*00001,其中0是己方棋子，*是空白，而1是对方棋子，这样并不是活4，而是冲4
                    case 5:
                        result = Lian.three // 冲4
                    case 4:
                        result = Lian.three // 冲4
                    default:
                        result = 0
                    }
                }
                else if block == 2 {
                    switch count {
                    case 6,5,4:
                        result = Lian.three // 冲4
                        break
                    default:
                        result = 0
                    }
                }
            }
        }
        else if empty == 3 || empty == count - 3 {
            if count >= 8 {
                result = Lian.five
            }
            else {
                if block == 0 {
                    switch count {
                    case 7:
                        result = Lian.four
                    case 6:
                        result = Lian.three
                    default:
                        result = 0
                    }
                }
                else if block == 1 {
                    switch count {
                    case 7:
                        result = Lian.four
                    case 6:
                        result = Lian.three
                    default:
                        result = 0
                    }
                }
                else if block == 2 {
                    switch count {
                    case 7,6:
                        result = Lian.three
                    default:
                        result = 0
                    }
                }
            }
        }
        else if empty == 4 || empty == count - 4 {
            if count >= 9 {
                result = Lian.five
            }
            else {
                if count == 8 {
                    if block <= 1 {
                        result = Lian.four
                    }
                    else {
                        result = Lian.three
                    }
                }
            }
        }
        else if empty == 5 {
            result = Lian.five
        }
        return result
    }
    // 只更新某个方向的得分，comScore[i][j][0...4],第3维的0...3分别表示4个方向的得分，而4表示总分
    // 考虑remove的时候，p(x,y)就是空点，empty = 0
    func update(board:[[Role]], p: Position,did: Int, player: Role) {
        var count: Int = 1, emptyPos: Int = 0, block: Int = 0,x : Int = 0, y: Int = 0
        var nx: Int = 0, ny: Int = 0
        // list 保存p点 did方向的所有元素，他们组成的连棋都是相同得分
        var list = [Position]()
        // put
        if (board[p.x][p.y] == player) {
            list.append(p)
        }
        // remove, reset, 该点就是empty点
        else {
            pScore[p.x][p.y][did] = 0
            emptyPos = 0
            count = 0
        }
        
        for i in 2 * did..<2 * did + 2 {
            for j in 1..<N {
                x = p.x + j * direction[i][0]
                y = p.y + j * direction[i][1]
                nx = x + direction[i][0]
                ny = y + direction[i][1]
                
                if !inBoard(x: x, y: y) || board[x][y] == AI.opponent(player: player) {
                    block += 1
                    break
                }
                if board[x][y] == player {
                    count += 1
                    if i % 2 == 1 && emptyPos != -1 {
                        emptyPos += 1
                    }
                }
                else {
                    // 中间隔了一个空子
                    if emptyPos == -1 && inBoard(x: nx, y: nx) && board[nx][ny] == player {
                        // 表示往负的方向走, 所以empty的位置是第一个
                        if i % 2 == 1 {
                            emptyPos = 0
                        }
                            // 表示正的方向
                        else {
                            emptyPos = count
                        }
                    }
                    else {
                        break
                    }
                }
                list.append(Position(x: x, y: y))
            }
        }
        let didScore = calculate(count: count, empty: emptyPos, block: block)

        // 更新list数组的点的得分
        for pos in list {
            // update 4's direction sum
            pScore[pos.x][pos.y][4] += didScore - pScore[pos.x][pos.y][did]
            // update did direction score
            pScore[pos.x][pos.y][did] = didScore
        }
    }
    func positionEvaluate(board: [[Role]], p: Position, player: Role) -> Int {
        pEvaluate += 1
        var sum = 0
        var count: Int = 1, emptyPos: Int = -1, block: Int = 0,x : Int = 0, y: Int = 0
        
        // 横，竖，撇，捺
        for i in 0..<direction.count {
            // 起始方向，初始化
            if i % 2 == 0 {
                count = 1
                emptyPos = -1
                block = 0
            }
            for j in 1..<N {
                x = p.x + j * direction[i][0]
                y = p.y + j * direction[i][1]
                let nextX = x + direction[i][0]
                let nextY = y + direction[i][1]
                // 被墙或者是对手的棋子堵了
                if !inBoard(x: x, y: y) || board[x][y] == AI.opponent(player: player){
                    block += 1
                    break
                }
                //己方棋子
                if board[x][y] == player {
                    count += 1
                    // i%2 = 1表示和i%2 =0 的反方向，必须有个区分
                    if i % 2 == 1 && emptyPos != -1 {
                        emptyPos += 1
                    }
                }
                // empty
                else {
                    // 中间隔了一个空子
                    if emptyPos == -1 && inBoard(x: nextX, y: nextY) && board[nextX][nextY] == player {
                        // 表示往负的方向走, 所以empty的位置是第一个
                        if i % 2 == 1 {
                            emptyPos = 0
                        }
                        // 表示正的方向
                        else {
                            emptyPos = count
                        }
                    }
                    else {
                        break
                    }
                }
            }
            if (i % 2 == 1) {
                sum += calculate(count: count, empty: emptyPos, block: block)
            }
        }
        return sum
    }
    
    // when one position is put chess, update the 4 direction positions
    func update(board: [[Role]],p: Position,player: Role) {
        for i in 0..<4 {
            update(board: board, p: p, did: i, player: player)
        }
        // for remove
        if (board[p.x][p.y] == Role.empty) {
            pScore[p.x][p.y][4] = 0
        }
    }
    
    func score(board: [[Role]]) -> Int {
        scoreCnt += 1
        var cMaxScore = -Lian.five
        var hMaxScore = -Lian.five
        
        if (scoreCache[zobrist.code] != nil) {
            hitCache += 1
            return scoreCache[zobrist.code]!
        }
        
        for i in 0..<N {
            for j in 0..<N {
                if board[i][j] == Role.computer {
                    cMaxScore = pScore[i][j][4] > cMaxScore ? pScore[i][j][4] : cMaxScore
                }
                else if board[i][j] == Role.human {
                    hMaxScore = pScore[i][j][4] > hMaxScore ? pScore[i][j][4] : hMaxScore
                }
            }
        }
        let x = cMaxScore - hMaxScore
        scoreCache[zobrist.code] = x
        return x
    }
    
    func max( board: inout [[Role]],deep: Int, alpha: Int, beta: Int) -> Int {
        searchCnt += 1
        var v: Int = score(board: board)
        let result = win(board: board)
        if deep <= 0 || result != Role.empty {
            return v
        }
        
        let positions = generatePositions(board: board, deep: deep)
        var best:Int = MIN
        
        for p in positions {
            go(board: &board, player: Role.computer, p: p)
            v = min(board: &board , deep: deep - 1, alpha: alpha, beta: (best > beta ? best : beta))
            remove(board: &board, p: p)
            
            if (best < v) {
                best = v
            }
            // 如果当前计算的是p节点,父节点为p.parent，p.children为儿子节点，如果当前计算的p.child儿子节点为8，而p的父节点当前最小为7了，那么久不必计算p.的其他儿子节点了，因为p的值是等于儿子中最大的，所以，可以break，剪枝
            if (v > alpha) {
                ABcut += 1
                break;
            }
        }
        return best
    }
    
    func min( board: inout [[Role]],deep: Int, alpha: Int, beta: Int) -> Int {
        searchCnt += 1
        var v = score(board: board)
        let result = win(board: board)
        
        if deep <= 0 || result != Role.empty {
            return v
        }
        let positions = generatePositions(board: board,deep: deep)
        var best: Int = MAX
        
        for p in positions {
            go(board: &board, player: Role.human, p: p)
            v = max(board: &board, deep: deep - 1, alpha: (best > alpha ? alpha : best), beta: beta)
            remove(board: &board, p: p)
            
            if best > v {
                best = v
            }
            // 如果当前计算的最小值，如果是8，都比该节点的父节点的值9要小，那么这一层的最小值肯定不超过8，那么就可以剪掉
            if v <  beta {
                ABcut += 1
                break;
            }
        }
        return best
    }
    static func opponent(player: Role) -> Role {
        if player == Role.computer {
            return Role.human
        }
        else if player == Role.human {
            return Role.computer
        }
        return Role.empty
    }
    

    func inBoard(x: Int,y: Int) -> Bool {
        if x < 0 || x >= N || y < 0 || y >= N {
            return false
        }
        return true
    }
    func hasNeayby(board: [[Role]],p: Position,dis: Int) -> Bool {
        for i in 0..<direction.count {
            for j in 1...dis {
                let x = p.x + j * direction[i][0]
                let y = p.y + j * direction[i][1]
                if !inBoard(x: x, y: y) {
                    break
                }
                if board[x][y] != Role.empty {
                    return true
                }
            }
        }
        return false
    }
    // 根据当前的棋局，生成对应的可选的点，离棋局中的点不超过2的距离的点
    func generatePositions(board: [[Role]],deep: Int) -> [Position] {
        
        var oneStep = [Position]()
        var twoStep = [Position]()
        var fives = [Position]()
        var fours = [Position]()
        var threes = [Position]()
        var twos = [Position]()
        for i in 0..<N {
            for j in 0..<N {
                if (board[i][j] == Role.empty) {
                    let p = Position(x: i,y: j)
                    if hasNeayby(board: board, p: p, dis: 1){
                        let computerScore  = positionEvaluate(board: board, p: p, player: Role.computer)
                        let humanScore = positionEvaluate(board: board, p: p, player: Role.human)
                        
                        if computerScore >= Lian.five {
                            fives.append(p)
                            return fives
                        }
                        else if (humanScore >= Lian.five) {
                            // 电脑可能还有其他的点可以直接赢
                            fives.append(p)
                        }
                        else if computerScore >= Lian.four {
                            // 要赢，插在最前面
                            fours.insert(p, at: 0)
                        }
                        else if humanScore >= Lian.four {
                            // 可能需要防守了
                            fours.append(p)
                        }
                        else if computerScore >= 2 * Lian.three {
                            fours.append(p)
                        }
                        else if humanScore >= 2 * Lian.three {
                            fours.append(p)
                        }
                        else if computerScore == Lian.three {
                            threes.insert(p, at: 0)
                        }
                        else if humanScore == Lian.three {
                            threes.append(p)
                        }
                        else if computerScore == Lian.two {
                            twos.insert(p, at: 0)
                        }
                        else if humanScore == Lian.two {
                            twos.append(p)
                        }
                        else {
                            oneStep.append(p)
                        }
                    }
                    else if deep >= 2 && hasNeayby(board: board, p: p, dis: 2) {
                        twoStep.append(p)
                    }
                }
            }
        }
        if fives.count > 0 {
            return fives
        }
        if fours.count > 0 {
            return fours
        }
        if threes.count > 0 {
            return threes
        }
        twos.append(contentsOf: oneStep)
        twos.append(contentsOf: twoStep)
        return twos
    }
    
    func isFive(board: [[Role]],p: Position, role: Role) -> Bool {
        var count: Int = 0
        for i in 0..<direction.count {
            if i % 2 == 0 {
                count = 1
            }
            for j in 1..<N {
                let x = p.x + j * direction[i][0]
                let y = p.y + j * direction[i][1]
                
                if !inBoard(x: x, y: y) || board[x][y] != role {
                    break;
                }
                count += 1
            }
            if count >= 5 {
                return true
            }
        }
        return false
    }
    
    func win(board: [[Role]]) -> Role {

        for i in 0..<N {
            for j in 0..<N {
                if board[i][j] != Role.empty{
                    let role: Role = board[i][j]
                    let gameOver = isFive(board: board, p: Position(x: i, y: j), role: role)
                    if gameOver {
                        return role
                    }
                }
            }
        }
        return Role.empty
    }
    
    func toKill(board: inout [[Role]]) -> Position {
        var positions = [Position]()
        
        let randomIdx: Int = Int(arc4random_uniform(UInt32(positions.count)))
        return positions[randomIdx]
    }
    
    func display(matrix: [[Int]]) {

        for i in 0..<matrix.count {
            for j in 0..<matrix[0].count {
                print(matrix[i][j])
            }
            
            print("\n")
        }
        
    }
}
